﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * 
     * 
By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

     * */
    class Problem85 : IProblem
    {
        public string Calculate()
        {
            //rjesenje je ono koje je najblize ispod targeta, s tim da je i(i+1)*j(j+1) / 4 = broj kvadrata
            int maxX = 0;
            int maxY = 0;

            int best = 8000000;
            int target = 8000000;

            int x = 53;
            int y = 52;

            while (true)
            {
                int test = x * y * (x + 1) * (y + 1);

                if (test > target)
                {  
                    y--;
                }
                else
                {
                    if (target - test < best)
                    {
                        best = target - test;
                        maxX = x;
                        maxY = y;
                    }
                    x++;
                }

                if (y == 1)
                    break;

            }
            Console.WriteLine("{0} x {1}: {2}", maxX, maxY, maxX * maxY * (maxX + 1) * (maxY + 1));

            return (maxX * maxY).ToString();
        }
    }
}
